﻿#include<iostream>
using namespace std;
const int N = 100010;
int q[N];
int temp[N];
int n;

void merge_sort(int q[], int l, int r)
{
	if (l >= r)return;

	int mid = l + r >> 1;		//找一个中间值
	merge_sort(q, l, mid);		//递归排序左边	
	merge_sort(q, mid + 1, r);	//递归排序右边
	int k = 0;		 //用来记录temp数组中值的个数
	int i = l;		 //指向左边数组中的最小值
	int j = mid + 1; //指向右边数组中的最小值
	while (i <= mid && j <= r)	//比较左右两个序列的值放入temp数组中
	{
		if (q[i] <= q[j])temp[k++] = q[i++];
		else temp[k++] = q[j++];
	}
	//比较完成后将其未比较的数继续放入temp数组中
	while (i <= mid)temp[k++] = q[i++];
	while (j <= r)temp[k++] = q[j++];

	//将temp数组中的值，放回q数组中
	for (i = l, j = 0; i <= r; i++, j++)q[i] = temp[j];
}
int main()
{
	cout << "案例一" << endl;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> q[i];

	merge_sort(q, 0, n - 1);

	for (int i = 0; i < n; i++)cout << q[i] << " ";

	system("pause");
	return 0;
};